package com.demo.algorithm.binary04;

/**
 * Author:       zhangshaoyang
 * Description:
 * 一、寻找一个数（基本的二分搜索）搜索一个数，如果存在，返回其索引，否则返回 -1。
 * 二、寻找左侧边界的二分搜索
 * 三、寻找右侧边界的二分查找
 * Date:         2021/6/8 8:47 上午
 */
public class FindNum {
    /**
     * 一、寻找一个数（基本的二分搜索）搜索一个数，如果存在，返回其索引，否则返回 -1。
     *
     * @param nums
     * @param target
     * @return
     */
    private static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 直接返回
                return mid;
            }
        }
        // 直接返回
        return -1;
    }

    /**
     * 二、寻找左侧边界的二分搜索
     *
     * @param nums
     * @param target
     * @return
     */
    private static int left_bound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定左侧边界，这样就不会立即返回找到的值，而是往左边继续找
                right = mid - 1;
            }
        }
        // 最后要检查left越界的情况
        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    /**
     * 三、寻找右侧边界的二分查找
     *
     * @param nums
     * @param target
     * @return
     */
    private static int right_bound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定右侧边界，这样就不会立即返回找到的值，而是往右边继续找
                left = mid + 1;
            }
        }
        // 最后要检查right越界的情况
        if (right >= nums.length || nums[right] != target) {
            return -1;
        }
        return right;

    }


    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10};
        int target = 4;
        System.out.println("binarySearch(nums,target) = " + binarySearch(nums, target));
        System.out.println("left_bound(nums,target) = " + left_bound(nums, target));
        System.out.println("right_bound(nums,target) = " + right_bound(nums, target));
    }
}
